package MiddlePractice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Demo39 {
	
//	39. 组合总和
//	给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。
//
//	candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。 
//
//	对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
	
//	public List<List<Integer>> combinationSum(int[] candidates, int target) {
//		
//    }
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		int n = candidates.length;
		List<List<Integer>>[][] dp = new LinkedList[n+1][target+1];
		
		for(int i=0; i<=n; i++) {
			Arrays.fill(dp[i], new LinkedList<>());
		}
		
		for(int i=0; i<=n; i++) {
			dp[i][0].add(new LinkedList<>());
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=target; j++) {
				
				if(j < candidates[i-1]) {
					dp[i][j] = dp[i-1][j];
				}
				else {
//					dp[i][j-candidates[i-1]] + dp[i-1][j];
					List<List<Integer>> newList = new LinkedList<>();
					List<List<Integer>> list = dp[i][j-candidates[i-1]];
					
					for(List<Integer> l : list) {
						List<Integer> one = new LinkedList<Integer>();
						for(Integer num : l) {
							one.add(num);
						}
						one.add(candidates[i-1]);
						newList.add(one);
					}
					
					List<List<Integer>> list2 = dp[i-1][j];
					for(List<Integer> l : list2) {
						List<Integer> one = new LinkedList<Integer>();
						for(Integer num : l) {
							one.add(num);
						}
						newList.add(one);
					}
					
					dp[i][j] = newList;
				}
			}
		}
		
		List<List<Integer>> ans = new LinkedList<>();
		for(List<Integer> l : dp[n][target]) {
			int sum = 0;
			for(Integer num : l) {
				sum += num;
			}
			if(sum == target) {
				ans.add(l);
			}
		}
		
		
		return ans;
		
    }

}
